package com.zan.onelevel.level1;

/**
 * @Author Zan
 * @Date 2023/11/29 14:46
 * @Description : 传入一个数组，将其转换成单链表
 */
public class BasicLink {

    public static class Node {
        public int x;
        public Node next;

        public Node(int x) {
            this.x = x;
            next = null;
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5, 6};
        Node head = initLinkedList(a);
        System.out.println(head);
        System.out.println(getListLength(head));
//        Node node = insertNodeByHead(head, new Node(7));

//        Node node1 = insertNodeByPosition(head, new Node(8), 3);

//        Node node2 = insertByEnd(head, new Node(9));
//        System.out.println(node);
//        System.out.println(node1);
//        System.out.println(node2);

//        Node node = insertNode(head, new Node(10), 7);

//        Node node = deleteByHead(head);

//        Node node = deleteByEnd(head);

//        Node node = deleteByPosition(head, 3);

        Node node = deleteNode(head, 6);

        System.out.println(node);
    }

    public static Node initLinkedList(int[] array) {
        Node head = null, current = null;
        for (int i = 0; i < array.length; i++) {
            Node newNode = new Node(array[i]);
            if (i == 0) { // 头节点
                // 由于head = current，因此当current在变化的时候，head也在变化
                head = newNode;
//                newNode = new Node(array[i]); // 如果在此将newNode重新定义，指向的是不同的堆数据，因此head就只是一个Node普通对象，单节点的链表
                current = newNode;
            } else { // 后面的节点
                current.next = newNode;
                current = newNode;
            }
        }
        return head;
    }

    /**
     * 遍历链表，获取链表的长度
     *
     * @param head 头节点
     * @return
     */
    public static int getListLength(Node head) {
        int length = 0;
        Node node = head;
        while (node != null) {
            length++;
            node = node.next;
        }
        return length;
    }

    /**
     * 在链表的表头插入
     *
     * @param head       原链表
     * @param nodeInsert 要插入表头的结点元素
     * @return
     */
    public static Node insertNodeByHead(Node head, Node nodeInsert) {
        nodeInsert.next = head;
        head = nodeInsert;
        return head;
    }

    /**
     * 在链表的中间位置插入
     *
     * @param head       原链表的头结点
     * @param nodeInsert 要插入的结点
     * @param position   要插入的位置，从1开始
     * @return
     */
    public static Node insertNodeByPosition(Node head, Node nodeInsert, int position) {
        Node newNode = head; // 不对原链表进行操作，用新链表指向堆中的同一个元素，进行堆中的操作
        int i = 1;
        while (i < position - 1) { // 要在中间位置插入，因此要获取插入位置的前一个结点，这样子才能将next连接起来
            newNode = newNode.next;
            i++;
        }
        nodeInsert.next = newNode.next; // 将要插入的结点的next指向插入位置前一个结点的next
        newNode.next = nodeInsert; // 将插入位置前一个结点的next指向要插入的结点
        return head;
    }

    /**
     * 在链表的结尾插入
     *
     * @param head       原链表的头结点
     * @param nodeInsert 要插入的结点
     * @return
     */
    public static Node insertByEnd(Node head, Node nodeInsert) {
        // 获取到原链表的元素个数，循环遍历找到最后一个结点，将最后一个结点的next指向新结点
        Node newNode = head;
        int nodeLength = getListLength(newNode);
        int i = 1;
        while (i < nodeLength) {
            newNode = newNode.next;
            i++;
        }
        newNode.next = nodeInsert;
        return head;
    }

    /**
     * 链表的插入（所有情况，表头、中间、结尾）
     * @param head 原链表
     * @param nodeInsert 插入的结点
     * @param position 插入的位置，从1开始
     * @return
     */
    public static Node insertNode(Node head, Node nodeInsert, int position) {
        // head原链表中没有数据，插入的结点就是链表的头结点
        if (head == null) {
            return nodeInsert;
        }

        // 获取存放元素个数 - 进行校验(position在[1, size]之间)
        int size = getListLength(head);
        if (position > size + 1 || position < 1) {
            System.out.println("位置参数越界");
            return head;
        }

        // 表头插入
        if (position == 1) {
            nodeInsert.next = head;
            head = nodeInsert;
            return head;
        }

        // 中间插入和结尾插入
        Node newNode = head;
        int count = 1;
        while (count < position - 1) {
            count++;
            newNode = newNode.next;
        }
        nodeInsert.next = newNode.next;
        newNode.next = nodeInsert;

        return head;
    }

    /**
     * 删除表头结点
     * @param head 原链表
     * @return
     */
    public static Node deleteByHead(Node head) {
        head = head.next;
        return head;
    }

    /**
     * 删除最后一个结点
     * @param head 原链表
     * @return
     */
    public static Node deleteByEnd(Node head) {
        Node newNode = head;
        int size = getListLength(head);
        int i = 1;
        while (i < size - 1) {
            i++;
            newNode = newNode.next;
        }
        newNode.next = null;
        return head;
    }

    /**
     * 删除中间结点
     * @param head 原链表
     * @return
     */
    public static Node deleteByPosition(Node head, int position) {
        Node newNode = head;
        int i = 1;
        while (i < position - 1) {
            i++;
            newNode = newNode.next;
        }
        newNode.next = newNode.next.next;
        return head;
    }

    /**
     * 删除结点（三种情况，表头、中间、最后一位结点）
     * @param head 原链表
     * @return
     */
    public static Node deleteNode(Node head, int position) {
        // 如果没有结点，说明无法删除，直接返回null即可
        if (head == null) {
            return null;
        }

        //校验
        int size = getListLength(head);
        if (position > size || position < 1) { // 这里不是size+1，而插入是size+1，因为插入可以插入到最后一位（未知的最后一位），而删除必须要是已知的，不能是未知的越界
            System.out.println("输入的参数有误");
            return head;
        }

        if (position == 1) { // 删除头节点
            return head.next;
        } else { // 删除中间结点或者最后一个结点
            Node newNode = head;
            int count = 1;
            while (count < position - 1) {
                count++;
                newNode = newNode.next;
            }
            newNode.next = newNode.next.next;
            return head;
        }
    }
}
